package com.heima.leetcode.practice;

import java.util.Arrays;
import java.util.HashMap;

/**
 * 小镇法官 997
 * @author 勾新杰
 * @version 1.0
 * @date 2024/10/17 18:24
 */
public class E997 {

    /**
     * <h3>方法一：出度入度法，性能好</h3>
     * 出度表示这个人有相信的人，入度表示有人相信当前这个人
     * @param n 小镇里的n个人
     * @param trust  trusted trust[i] = [a, b] 表示 a  相信 b
     * @return 小镇法官
     */
    public int findJudge1(int n, int[][] trust) {
        // 统计每个人的出度和入度
        int[] inDegree = new int[n + 1];
        int[] outDegree = new int[n + 1];
        for (int[] arr : trust) {
            outDegree[arr[0]]++;
            inDegree[arr[1]]++;
        }
        // 寻找入度为n - 1并且出度为0的人，就是小镇法官
        for (int i = 1; i <= n; i++){
            if (inDegree[i] == n - 1 && outDegree[i] ==0){
                return i;
            }
        }
        // 没有法官
        return -1;
    }

    /**
     * <h3>方法二：哈希表，性能差</h3>
     * 思路：遍历trust，将trust[0]的值减一，trust[1]的值加一，最后遍历哈希表，如果某个值等于n-1，则返回该键值，否则返回-1。
     * @param n 小镇里的n个人
     * @param trust  trusted trust[i] = [a, b] 表示 a  相信 b
     * @return 小镇法官
     */
    public int findJudge2(int n, int[][] trust) {
        // 统计每个人的入度和出度之差，也就是相信他的人 - 他相信的人
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int[] arr : trust) {
            // 出度那一方减一
            map.put(arr[0], map.getOrDefault(arr[0], 0) - 1);
            // 入度那一方加一
            map.put(arr[1], map.getOrDefault(arr[1], 0) + 1);
        }
        // 遍历1 到 n，如果某个人对应的入度和出度之差等于n-1，则返回这个人，否则返回-1。
        for (int i = 1; i <= n; i++) {
            if (map.getOrDefault(i, 0) == n - 1) {
                return i;
            }
        }
        return -1;
    }

    /**
     * <h3>方法三：布尔数组法，性能最高</h3>
     * @param n 小镇里的人数
     * @param trust trusted trust[i] = [a, b] 表示 a  相信 b
     * @return 小镇法官
     */
    public int findJudge3(int n, int[][] trust) {
        // 创建一个长度为n+1的数组，用来标记是否是法官
        boolean[] isJudge = new boolean[n + 1];
        // 将数组初始化为true，表示默认都是法官
        Arrays.fill(isJudge, true);

        // 遍历trust，将trust[0]对应的人标记为false，表示不是法官
        for (int[] arr : trust) {
            isJudge[arr[0]] = false;
        }

        // 遍历isJudge，如果某个值是true，则将judge暂且设置为这个人
        // 经过一轮遍历后，只可能有一个人是候选法官
        // 因为如果有多个人同时是候选法官，那么其中肯定有多个还信任了其他人
        // 但是上述逻辑已经把信任其他人的情况除开了，造成了逻辑矛盾
        // 所以顶多只会有一个候选法官
        int judge = -1;
        for (int i = 0; i < isJudge.length; i++) {
            if (isJudge[i]){
                judge = i;
            }
        }

        // 法官还是-1，也就是里面没有候选法官
        if (judge == -1){
            return -1;
        }

        // 统计候选法官的入度个数，也就是统计相信这个人的人数
        int count = 0;
        for (int[] arr : trust) {
            if (arr[1] == judge){
                count++;
            }
        }

        // 如果count等于n-1，则返回法官，否则返回-1
        if (count == n - 1){
            return judge;
        } else {
            return -1;
        }
    }
}
